To accurately represent a color image using digital electronics, the image is quantized to discrete locations and colors. Typically, the image is separated into a two-dimensional array of picture elements or pixels, each of which is assigned a single color. This allows a computer system to represent a color image internally as a two-dimensional array of digital color values stored in a memory. Images represented in this manner are known as bitmapped images because one unit of memory (comprising a group of one or more data bits) is assigned or mapped to each pixel of the image.
The perceived quality of the digitized color image depends upon the color and spatial resolutions at which it is reproduced on an output device. Color resolution is measured by the number of colors that can be simultaneously used, or are "active" in the reproduced image. For example, an IBM-compatible personal computer with a VGA-based display system can simultaneously display 16 colors. A personal computer with a "super" VGA (SVGA)-based display system can display 256 colors simultaneously in an image. Spatial resolution is measured by the number of individual pixels that make up the reproduced image. For example, a computer with a VGA-based display system can display 640 horizontal by 480 vertical pixels (640.times.480) on screen in its highest graphics mode. Higher spatial resolutions may be achieved with display systems following the SVGA, XGA and other graphics standards. The higher the color and spatial resolutions of the reproduced image, the better its perceived image quality.
Color resolution is equivalently measured by the number of data bits for storing each pixel of the image in a computer's video memory (also known as the bit "depth" of the frame display buffer). The number of colors that can be used simultaneously in a reproduced image is related to the number of data bits mapping to each pixel by the function 2.sup.N where N is the number of data bits. Thus, display systems with four bits per pixel can display only 16 simultaneous colors. Which 16 colors (out of the millions possible) are simultaneously displayed depends on the contents of a color look-up table (CLUT) that is addressed by the four-bit color values. The particular set of 16 colors within the look-up table is referred to as a displayable color palette. It is generally possible to switch palettes to emphasize colors tailored to individual images on the display. For example, one color palette may better portray a polar bear in a snowstorm while another palette may better portray a grizzly bear in a forest. As the number of bits per pixel grows from four to eight to twelve, etc., the size of the displayable color palette and the number of simultaneously displayable colors grows exponentially according to the function, 2.sup.N.
However, application program interfaces provided by operating systems software can often support a much larger number of active colors than supported by VGA, SVGA and other low-bit display standards. The Microsoft.RTM. Windows.TM. operating system, for example, supports over 16 million active colors. An application such as a paint program using the Windows.TM. operating system can specify 24-bits for each pixel of an image. Typically, the 24-bit value is an RGB (for red, green and blue) value comprising an ordered triple of three eight bit values, one eight bit value in each color dimension of red, green, and blue. The RGB value specifies colors according to the intensities of red, green, and blue (which are additive primary colors) that are mixed to form the color. Each eight bit value represents an intensity level of the respective color between 0 (zero intensity) and 1 (full intensity). Red, for example has an RGB value of (1,0,0) while purple, which is half intensity red and half-intensity blue, has an RGB value of (1/2, 0, 1/2).
The red-green-blue (RGB) color model (which specifies colors with RGB ordered triples as described above) is typically used by computers to quantize colors because it corresponds directly to the range of colors or color gamut that is displayable on a computer monitor. Typical monitors have a set of three phosphors, one red, one green and one blue, at each pixel location on their display. Each pixel on the monitor can display a gamut of colors falling within a three dimensional cube defined by red, green and blue intensities between 0 and 1. Other color quantization models are also used and may be more suitable in certain applications. However, all the color models use a three dimensional representation of the color range, or gamut.
State-of-the-art display systems which go well beyond VGA and SVGA typically have 24 (or more) bits per pixel for displaying about 16.8 million colors simultaneously. They also provide a spatial resolution of 1280.times.1024 or higher. Such display systems are known as "true color" systems because they allow the actual color to be specified accurately and independently for each pixel. True color systems do not require color look-up tables because the values stored in the screen memory for each pixel directly indicate the color to appear on the screen (e.g. the RGB value specifying the color is itself stored in the screen memory for each pixel). Because the pixel colors are directly indicated by the stored value, the colors are said to be "direct mapped."
However, a major drawback of true color display systems is their cost. They require significantly increased amounts of video memory for a display buffer and may also employ accelerator devices. For desired spatial resolutions of 1024.times.768 or higher, such systems can cost as much or more than an otherwise state-of-the art personal computer system. True color systems may also perform at slower speeds than 8-bit display systems. It is therefore often desirable to reproduce true color images (or any image stored at high color resolution) using display systems (or other output devices) that use a lower color resolution while maintaining image quality.
In the prior art there have been different approaches taken to provide acceptable quality images without the cost of true color systems. One approach, mentioned above, is to vary the displayable color palette depending on the colors in an image to be displayed. By choosing an optimal selection of colors for a palette, the quality of the reproduced image can be greatly enhanced. One such technique is known as the popularity algorithm. This technique chooses as colors for a palette, those colors which occur most frequently in the image being reproduced. For example, for 8-bit color resolution reproductions, the 256 colors used most frequently in the image are chosen to fill the color palette. When the image is reproduced, each color in the image is mapped to the nearest color in the palette. Usually, the quality of the resulting image is improved since the true color of most of the image's pixels will be in the palette.
Such adaptive palette techniques, however, produce undesirable effects in a windowing environment in which several images may be simultaneously displayed. Since all images on the display use the same palette, adapting the color palette to an individual image on the display generally degrades the quality of the remaining images. Also, when the focus of the windowing environment is subsequently changed to another individual image on the display, the color palette must be re-adapted to that image. Consequently, the quality of the previous image becomes degraded in what is known as a palette war.
A second approach is to truncate the 24 bits per pixel to eight or four bits by simply removing a sufficient number of least significant bits from each color dimension. The problem with truncation is that the color information of the truncated bits is lost. As a result, there is significant difference or error between the color of pixels in the reproduced image from their true color which reduces image quality.
Another approach, known as "ordered dithering," relies on the eye's ability to blend the colors of adjacent pixels over small spatial areas so that an intermediate color is perceived. This approach focuses on replacing or mapping non-displayable colors (those not in the displayable color palette) within defined areas of the image to displayable colors to best simulate the true color when viewed by the human eye. Ordered dithering takes into account additional factors in determining the replacement color, such as the relative location of the pixel being dithered within the image.
Yet another approach is "error diffusion" dithering. Error diffusion is a process for spreading, or diffusing, the error between the true color of a pixel and the displayable color with which it is reproduced to neighboring pixels in the image. Common error diffusion techniques include the Floyd-Steinberg filter, the Stucki filter, and the Burkes filter.
Although prior 4 and 8-bit display systems using these approaches work to some degree, none has proven to be a satisfactory substitute for a true color system. Each produces artifacts, or unwanted visual byproducts, when an image is displayed with a spatial resolution of 60 pixels per inch or greater (640.times.480 on a 13" monitor or 1024.times.768 on a 19" monitor). An object of this invention, therefore, is to provide a suitable technique for displaying near true color images using a minimum number of bits per pixel.